package B刷题.二叉树;

import java.util.*;

/**
 * @author wei.zhao
 * @description: 剑指 Offer 68 - II.二叉树的最近公共祖先
 * @date 2022年11月11日 16:08
 */
public class Code08_LowestCommonAncestor {

    /**
     * 方法一：分别找出两个节点的所有父节点，找第一个相交节点。
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        HashMap<TreeNode, TreeNode> parentMap = new HashMap<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        parentMap.put(root, null);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop.right != null) {
                parentMap.put(pop.right, pop);
                stack.add(pop.right);
            }
            if (pop.left != null) {
                parentMap.put(pop.left, pop);
                stack.add(pop.left);
            }
        }
        List<TreeNode> pParent = new ArrayList<>();
        Set<TreeNode> qParent = new HashSet<>();
        while (p != null) {
            pParent.add(p);
            p = parentMap.get(p);
        }
        while (q != null) {
            qParent.add(q);
            q = parentMap.get(q);
        }
        for (TreeNode treeNode : pParent) {
            if (qParent.contains(treeNode)) {
                return treeNode;
            }
        }
        return null;
    }

    /**
     * 方法二：二叉树的递归套路
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        Info info = process(root, p, q);
        return info.result;
    }

    public Info process(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return new Info(false, false, null);
        }
        Info left = process(root.left, p, q);
        if (left.result != null) {
            return new Info(null, null, left.result);
        }
        Info right = process(root.right, p, q);
        if (right.result != null) {
            return new Info(null, null, right.result);
        }
        Info info = new Info(false, false, null);
        if (left.hasP || right.hasP || root == p) {
            info.hasP = true;
        }
        if (left.hasQ || right.hasQ || root == q) {
            info.hasQ = true;
        }
        if (info.hasP && info.hasQ) {
            info.result = root;
        }
        return info;
    }

    public static class Info {
        private Boolean hasP;
        private Boolean hasQ;
        private TreeNode result;

        public Info(Boolean hasP, Boolean hasQ, TreeNode result) {
            this.hasP = hasP;
            this.hasQ = hasQ;
            this.result = result;
        }
    }

    /**
     * 方法三：巧妙解法
     */
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor3(root.left, p, q);
        TreeNode right = lowestCommonAncestor3(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

}
